package com.jia.leetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Pro0210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        Queue<Integer> queue = new LinkedList<Integer>();
        List<List<Integer>> adjacency = new ArrayList<List<Integer>>();
        for(int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<Integer>());
        }
        for(int[] p : prerequisites) {
            indegrees[p[0]] ++;
            adjacency.get(p[1]).add(p[0]);
        }
        for(int i = 0; i < indegrees.length; i++) {
            if(indegrees[i] == 0) {
                queue.add(i);
            }
        }
        int[] ans = new int[numCourses];
        int index = 0;
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            ans[index++] = cur;
            --numCourses;
            for(int next : adjacency.get(cur)) {
                if(--indegrees[next] == 0) {
                    queue.add(next);
                }
            }
        }
        return numCourses == 0 ? ans : new int[]{};
    }
}
